package 栈与队列;

/**
 * 力扣117：117. 填充每个节点的下一个右侧节点指针 II
 *给定一个二叉树：
 *
 * struct Node {
 *   int val;
 *   Node *left;
 *   Node *right;
 *   Node *next;
 * }
 * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。
 *
 * 大致思路：
 *  主要是通过前驱指针来实现，通过前驱指针prev和辅助节点dummy，采用BFS层级遍历的思想，来遍历每一层根节点；
 *  通过prev指针来记录当前节点的前驱节点，通过dummy指针来辅助构建下一层链表；
 * 解题步骤：
 * 1：初始化：从根节点开始处理，如果根节点为空，直接返回；
 * 2：逐层处理：使用一个虚拟节点（dummy）来辅助构建下一层链表，虚拟节点可以帮助我们处理下一层节点的连接，避免复杂的边界处理条件；
 * 3：连接到子节点：遍历当前层的每一个节点，将它们的左子节点和右子节点依次连接到下一层链表中；
 * 4：移动到下一层，处理完当前层后，将当前层移动到下一层的头结点，继续处理，直到没有下一层为止；
 *
 */
public class L_117 {

    /**
     * 代码解释
     * 虚拟节点（dummy）：用于简化下一层链表的构建过程，作为下一层链表的头节点前驱。
     * prev指针：指向当前正在构建的下一层链表的最后一个节点，用于连接新的子节点。
     * 外层循环：处理每一层，直到没有更多的层需要处理。
     * 内层循环：遍历当前层的每个节点，将它们的左子节点和右子节点连接到下一层链表中，并更新prev指针。
     * 重置操作：处理完当前层后，将current指向下一层的头节点，并重置dummy和prev，以便处理下一层。
     *
     * 这种方法通过逐层处理节点，确保每个节点的next指针正确指向右侧节点，同时保持了O(1)的空间复杂度。
     * @param root
     * @return
     */
    public Node connect(Node root) {
        if(root == null){
            return null;
        }
        Node current = root;
        Node dummy = new Node(0); // 虚拟头结点，用于构建下一层链表
        Node prev = dummy; // 定义前驱节点
        // 外层循环，处理每一层
        while (current != null){
            // 内层循环，处理当前层的每个节点，将下一层节点连接成链表
            while (current != null){
                if(current.left != null){
                    prev.next = current.left;
                    prev = prev.next;
                }
                if(current.right != null){
                    prev.next = current.right;
                    prev = prev.next;
                }
                current = current.next; // 移动当前层的下一个节点
            }

            // 处理完当前层节点后，移动到下一层，并进行重置操作
            current = dummy.next; // 移动到下一层链表的头结点 ，注意prev首次指向dummy
            dummy.next = null;
            prev = dummy; // 重置prev指针,开始构建下一层链表
        }
        return root;
    }


    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }
}
